#pragma
#include<iostream>

using namespace std;

enum Colour
{
	RED, BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _parent = nullptr;
	RBTreeNode<T>* _left = nullptr;
	RBTreeNode<T>* _right = nullptr;

	Colour _col = RED;
	T _Data;
	RBTreeNode(const T& data = T())
		:_Data(data){ }
};

template<class T,class Ptr,class Ref>
struct __Treeiterator
{

	typedef RBTreeNode<T> Node;
	typedef __Treeiterator<T, Ptr, Ref> self;
	typedef __Treeiterator<T, T*, T&> Iterator;

	__Treeiterator(Node* it)
		:_it(it){ }
	__Treeiterator(const Iterator& it)
		:_it(it._it){ }

	Ref operator*()
	{
		return _it->_Data;
	}

	Ptr operator->()
	{
		return &(_it->_Data);
	}
	
	bool operator!=(const self& it) const
	{
		return _it != it._it;
	}

	bool operator==(const self& it) const
	{
		return _it == it._it;
	}

	self operator++()
	{
		if (_it->_right)
		{
			Node* cur = _it->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_it = cur;
		}
		else
		{
			Node* cur = _it;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_it = cur;
		}

		return *this;
	}

	self operator--()
	{
		if (_it->_left)
		{
			Node* cur = _it->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_it = cur;
		}
		else
		{
			Node* cur = _it;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_it = cur;
		}

		return *this;
	}

	Node* _it = nullptr;
};


template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __Treeiterator<T, T*, T&> iterator;
	typedef __Treeiterator<T, const T*, const T&> const_iterator;

	iterator begin()
	{
		Node* maxleft = _root;
		while (maxleft && maxleft->_left)
		{
			maxleft = maxleft->_left;
		}
		return iterator(maxleft);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator begin() const
	{
		Node* maxleft = _root;
		while (maxleft && maxleft->_left)
		{
			maxleft = maxleft->_left;
		}
		return const_iterator(maxleft);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	iterator find(const K& data)
	{
		KeyOfT kt;
		Node* cur = _root;
		while (cur)
		{
			if (data > kt(cur->_Data))
			{
				cur = cur->_right;
			}
			else if (data < kt(cur->_Data))
			{
				cur = cur->_left;
			}
			else
			{
				return iterator(cur);
			}
		}
		return iterator(nullptr);
	}

	const_iterator find(const K& data) const
	{
		KeyOfT kt;
		Node* cur = _root;
		while (cur)
		{
			if (data > kt(cur->_Data))
			{
				cur = cur->_right;
			}
			else if (data < kt(cur->_Data))
			{
				cur = cur->_left;
			}
			else
			{
				return const_iterator(cur);
			}
		}
		return const_iterator(nullptr);
	}

	pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		Node* cur = _root;
		Node* parent = nullptr;

		KeyOfT kot;
		while (cur)
		{
			if (kot(data) > kot(cur->_Data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_Data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		cur = new Node(data);
		cur->_col = RED;

		Node* newnode = cur;

		if (kot(data) > kot(parent->_Data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = parent->_col = RED;
					}
					break;
				}

			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = BLACK;
						grandfather->_col = parent->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	int Height()
	{
		return Height(_root);
	}

	int Height(Node* _root)
	{
		if (_root == nullptr)
		{
			return 0;
		}

		int leftheight = Height(_root->_left);
		int rightheight = Height(_root->_right);


		return leftheight > rightheight ? leftheight+1 : rightheight+1;
	}

private:
	void RotateL(Node* parent)
	{

		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

		Node* ppnode = parent->_parent;

		parent->_parent = cur;


		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;

			}

			cur->_parent = ppnode;
		}
	}


	void RotateR(Node* parent)
	{

		Node* cur = parent->_left;
		Node* curright = cur->_right;

		parent->_left = curright;
		if (curright)
			curright->_parent = parent;

		Node* ppnode = parent->_parent;
		cur->_right = parent;
		parent->_parent = cur;

		if (ppnode == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}
	}
	Node* _root;
};



